#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

typedef struct node{    int data;     struct node *next;}   listnode, *linklist;

typedef int                                                 INT;
// 给int取个别名，叫INT
int a1;
INT a2;

typedef char *p;
// 给char *取个别名，叫p
char *k1;
p     k2;


// 创建一个新的节点
linklist new_node(int data)
{
    listnode *new = malloc(sizeof(struct node));
    if(new != NULL)
    {
        new->data = data;
        new->next = NULL;
    }
    return new;
}

// 判定指定单链表是否为空
bool is_empty(linklist head)
{
    return head==NULL;
}

// 查找尾节点
listnode *find_tail(struct node *head)
{
    if(is_empty(head))
        return NULL;

    struct node *tail = head;
    while(tail->next != NULL)
        tail = tail->next;

    return tail;
}

// 在指定的链表的末尾，添加一个节点new
void list_add(struct node **phead, struct node *new)
{
    // 空链表时，new就是唯一的节点，也是首节点
    if(is_empty(*phead))
    {
        *phead = new;
        return;
    }

    // 找到指向尾节点的指针tail
    struct node *tail = find_tail(*phead);
    
    // 将新节点new接入链尾
    tail->next = new;
}

void showList(struct node *head)
{
    if(is_empty(head))
        return;

    struct node *p;
    for(p=head; p!=NULL; p=p->next)
    {
        printf("%d\t", p->data);
    }
    printf("\n");
}

// 面试官希望得到的回答：快慢指针法寻找单链表中间节点
struct node * find_middle(struct node *head)
{
    // 小链表存放答案
    struct node *mid = NULL;

    struct node *slow = head;
    struct node *fast = head;

    while(fast!=NULL && fast->next!=NULL)
    {
        if(fast->next->next == NULL)
            list_add(&mid, new_node(slow->data));

        fast = fast->next->next;
        slow = slow->next;
    }

    list_add(&mid, new_node(slow->data));
    return mid;
}

int main(int argc, char const *argv[])
{
    struct node *head = NULL;

    // 首节点
    list_add(&head, new_node(1));
    list_add(&head, new_node(2));
    list_add(&head, new_node(3));
    list_add(&head, new_node(4));
    list_add(&head, new_node(5));
    // list_add(&head, new_node(6));

    // 遍历链表: 1 2 3 4 5
    showList(head);

    // 找到中间节点（1个/2个）
    struct node *mid = find_middle(head);
    for(;mid!=NULL; mid=mid->next)
        printf("mid: %d\n", mid->data);


    return 0;
}
